package kyssion.leetcode.num1_50;

import java.util.*;

/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。
 * <p>
 * 说明：
 * <p>
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1:
 * <p>
 * 输入: candidates = [2,3,6,7], target = 7,
 * 所求解集为:
 * [
 * [7],
 * [2,2,3]
 * ]
 * 示例 2:
 * <p>
 * 输入: candidates = [2,3,5], target = 8,
 * 所求解集为:
 * [
 * [2,2,2,2],
 * [2,3,3],
 * [3,5]
 * ]
 */
public class code39_组合总和 {
    public static void main(String[] args) {
        new code39_组合总和().combinationSum(
                new int[]{
                        2, 3, 5,6,7,8,9,10
                }, 1000
        );
    }

    int alls = 0;
    /**
     * 第一种写法使用递归,不进行缓存优化,时间负载度是阶乘级别的
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        candidates = deWeighting(candidates);
        Stack<Integer> stack = new Stack<>();
        List<List<Integer>> listList = new ArrayList<>();
        ans(candidates, stack, 0, target, listList);
        System.out.println(alls);
        return listList;
    }

    public void ans(int[] items, Stack<Integer> stack, int index, int target, List<List<Integer>> all) {
        if (target == 0) {
            all.add(new ArrayList<>(stack));
            return;
        }
        for (int a = index; a < items.length; a++) {
            alls++;
            if (target - items[a] >= 0) {
                stack.push(items[a]);
                ans(items, stack, a, target - items[a], all);
                stack.pop();
            }
        }
        return;
    }

    public int[] deWeighting(int[] candidates) {
        int index = 0;
        for (int a = 1; a < candidates.length; a++) {
            if (candidates[a] == candidates[a - 1]) {
                index++;
            }
            candidates[a - index] = candidates[a];
        }
        return Arrays.copyOfRange(candidates, 0, candidates.length - index);
    }


    /**
     * 第二种写法 dp写法事件复杂度 x*l
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        return new ArrayList<>();
    }
}
